package com.code.test.second.link;

public class SCode92 {

    public static void main(String[] args) {
        SNode head = new SNode(1);
        SNode second = new SNode(2);
        SNode third = new SNode(3);
        SNode n4 = new SNode(4);
        SNode n5 = new SNode(5);
        SNode n6 = new SNode(6);
        SNode n7 = new SNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        SNode s = reverseBetween(head, 2,4);
        int a = 2;

    }

    public static SNode reverseBetween(SNode head, int left, int right) {

        SNode dummyNode = new SNode(-1);
        dummyNode.next = head;

        SNode pre = dummyNode;
        // 找到left节点的前一个
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 找到right节点
        SNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 记下左节点和右节点，翻转完要挂上原来的节点
        SNode leftNode = pre.next;
        // right节点的下一个
        SNode rightNext = rightNode.next;

        // 切断链接，以防right之后继续反转
        pre.next = null;
        rightNode.next = null;

        SNode curSwap = leftNode;
        SNode swapPre = null;
        while (curSwap != null) {
            SNode tmp = curSwap.next;
            curSwap.next = swapPre;
            swapPre = curSwap;
            curSwap = tmp;
        }
        // 接回原来的链表中
        pre.next = rightNode;
        leftNode.next = rightNext;

        return dummyNode.next;
    }
}
